package com.zjj.algorithm.learning.atguigu.linkedlist;

import java.util.Arrays;
import java.util.Stack;

/**
 * 测试单链表
 * @author zjj_admin
 * @date 2022/11/1 16:50
 */
public class SingleLinkedListDemo {


    public static void main(String[] args) {
        SingleLinkedList linkedList = new SingleLinkedList();
        //先创建节点
        HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
        HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
        HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");

//        linkedList.addHero(hero1);
//        linkedList.addHero(hero3);
//        linkedList.addHero(hero2);
//        linkedList.addHero(hero4);


        linkedList.addHeroByOrder(hero1);
        linkedList.addHeroByOrder(hero3);
        linkedList.addHeroByOrder(hero2);
        linkedList.addHeroByOrder(hero4);
        linkedList.addHeroByOrder(hero2);

        //展示
        linkedList.show();

        System.out.println("逆序打印");
        int[] ints = SingleLinkedList.reversePrint(linkedList.head);
        System.out.println("ints = " + Arrays.asList(ints).toString());


//        System.out.println("将链表反转");
//        SingleLinkedList.reverseLinkedList(linkedList.head);
//        linkedList.show();
//        HeroNode newHero = new HeroNode(2, "小卢", "玉麒麟~~");
//        linkedList.updateHero(newHero);
//        System.out.println("修改后");
//        linkedList.show();
//
////        linkedList.deleteHero(hero4);
////        linkedList.deleteHero(hero2);
//
//        System.out.println("删除后");
//        linkedList.show();
//        int length = SingleLinkedList.getLength(linkedList.head);
//        System.out.println("length = " + length);
//
//        HeroNode res = SingleLinkedList.getLastIndexNode(linkedList.head, 3);
//        System.out.println("res = " + res);

    }
}


/**
 * 定义一个单链表，用于管理英雄节点
 */
class SingleLinkedList{

    /**
     * 头结点，不存储数据
     */
    public HeroNode head = new HeroNode(0,"","");

    /**
     * 添加一个英雄
     * 当我们不考虑排序时
     * 1、找到最后一个节点
     * 2、将最后一个节点的 next 指向新添加的节点
     * @param heroNode
     */
    public void addHero(HeroNode heroNode){
        //因为head节点不动，所以需要一个临时的节点，用于找到最后一个节点
        HeroNode temp = head;
        //找到最后一个节点
        while (true){
            if(temp.next == null){
                break;
            }
            //当没有遍历到最后一个节点时，将temp后移，直到最后一个节点
            temp = temp.next;
        }
        //将while结束时，temp就是最后一个节点，将temp的next给新添加的节点即可
        temp.next = heroNode;
    }


    /**
     * 添加节点，根据 No 的排序进行添加
     */
    public void addHeroByOrder(HeroNode heroNode){
        //依旧头节点不动，所以还是需要一个临时指针
        //单链表，temp位于添加位置的前一个节点
        HeroNode temp = head;

        //标识添加的英雄标号编号是否存在
        boolean flag = false;
        //首先需要找到新添加的节点应该添加在什么位置
        while (true){
            //此时添加的位置在最后一个节点
            if(temp.next == null){
                break;
            }
            //找到了需要添加的位置
            if(temp.next.no > heroNode.no){
                break;
            }
            //判断需要添加的位置是否和新加入的节点的编号是否相同
            // 这里必须是 temp.next.no 不能是 temp.no，否则可能死循环
            if(temp.next.no == heroNode.no){
                flag = true;
                break;
            }
            temp = temp.next;
        }

        if (flag) {
            System.out.println("存在需要相同的英雄，不能添加：" + heroNode.no);
            return;
        }
        //添加数据
        heroNode.next = temp.next;
        temp.next = heroNode;
    }


    /**
     * 修改节点信息，根据编号修改
     * @param newHeroNode
     */
    public void updateHero(HeroNode newHeroNode){
        if (this.head.next == null) {
            System.out.println("链表为空，不能修改");
            return;
        }
        HeroNode temp = head.next;
        //标注在链表中是否存在这个节点
        boolean flag = false;
        while (true){
            //当遍历结束都没找到
            if(temp == null){
                break;
            }
            //当找到了时
            if(temp.no == newHeroNode.no){
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (!flag) {
            System.out.println("不存在当前节点，不能修改");
            return;
        }
        temp.name = newHeroNode.name;
        temp.nickname = newHeroNode.nickname;
    }


    /**
     * 删除节点
     * 定义一个临时变量 temp，为需要删除节点的前一个节点
     * 删除核心代码为 temp.next = temp.next.next;
     * @param heroNode 需要删除的节点
     */
    public void deleteHero(HeroNode heroNode){
        HeroNode temp = head;
        //标记是否存在需要删除的数据
        boolean flag = false;
        while (true){
            if(temp == null){
                break;
            }
            if(temp.next.no == heroNode.no){
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (!flag) {
            System.out.println("不存在当前节点，删除失败");
            return;
        }
        //删除节点
        temp.next = temp.next.next;
    }

    /**
     * 返回链表的有效长度，不算头结点
     * @param head
     * @return
     */
    public static int getLength(HeroNode head){
        if(head.next == null){
            return 0;
        }
        int length = 0;
        HeroNode curr = head.next;
        while (curr != null){
            length ++;
            curr = curr.next;
        }
        return length;
    }


    /**
     * 查找单链表中倒数第 k 个节点【新浪面试题】
     * 1、编写一个方法接收head节点，同时接收一个 index，index表示倒数第 index 个节点
     * 2、先把链表从头到尾遍历，得到链表的总长度。
     * 3、得到 size 后，从链表的第1个开始遍历，遍历 （size -index） 个
     * 4、找到了就返回该节点，不然返回 null
     * @param head
     * @return
     */
    public static HeroNode getLastIndexNode(HeroNode head,int index){
        if(head.next == null){
            return null;
        }
        int length = getLength(head);
        if(index <= 0 || length < index){
            return null;
        }
        // 2 6 8 10 12 倒数第2个
        HeroNode curr = head.next;
        for (int i = 0;i < length - index ;i ++ ){
            curr = curr.next;
        }
        return curr;
    }


    /**
     * 将单链表反转 【腾讯面试题】
     * 思路：
     * 1、先定义一个头节点 reserveHead = new ...
     * 2、从头到尾遍历，将节点放在 reserveHead 的下一个节点
     * 3、将原来的 head.next = reserveHead.next
     * @param head
     * @return
     */
    public static void reverseLinkedList(HeroNode head){
        //判断链表的个数，当为 null 或者只有一个节点时直接返回
        if(head.next == null || head.next.next == null){
            return;
        }
        HeroNode curr = head.next;
        HeroNode next = null;
        HeroNode reserveHead = new HeroNode(-1,"","");
        while (curr != null){
            //首先保存下一个节点
            next = curr.next;
            //将 curr 的下一个节点放在 reserveHead 的后面
            curr.next = reserveHead.next;
            //让 curr 连在新的链表上
            reserveHead.next = curr;
            curr = next;
        }
        head.next = reserveHead.next;
    }


    /**
     * 逆序打印单链表
     * 方法1，现将链表逆序，在打印
     * 方法2：将链表数据依次压栈，然后取出
     * @param head
     */
    public static int[] reversePrint(HeroNode head){
        if(head.next == null){
            return new int[0];
        }
        Stack<HeroNode> stack = new Stack<>();
        HeroNode curr = head.next;
        while (curr != null){
            stack.push(curr);
            curr = curr.next;
        }
        int[] res = new int[stack.size()];
        int i = 0;
        while (!stack.empty()){
            HeroNode heroNode = stack.pop();
            res[i] = heroNode.no;
            i++;
            System.out.println(heroNode);
        }
        return res;
    }


    /**
     * 显示单链表中的数据，将链表中的数据全部打印
     *
     */
    public void show(){
        if (this.head.next == null){
            System.out.println("单链表中不存在节点");
            return;
        }
        //定义一个临时变量，用于存储头结点的下一个节点
        HeroNode temp = this.head.next;
        //依次遍历，将节点信息打印
        while (true){
            if(temp == null){
                break;
            }
            //打印
            System.out.println(temp);
            //将节点指向下一个节点
            temp = temp.next;
        }
    }





}

/**
 * 定义一个heroNode
 */
class HeroNode{


    /**
     * 此处定义为 public 是为了方便测试，真实环境不建议这样
     */
    public int no;
    public String name;
    public String nickname;
    /**
     * 下一个节点，当为 null时就表示为最后一个节点
     */
    public HeroNode next;


    public HeroNode(int no, String name, String nickname) {
        this.no = no;
        this.name = name;
        this.nickname = nickname;
    }


    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickname='" + nickname + '\'' +
                '}';
    }
}
